package com.xinheyun.demo.leetcode;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/31 9:50
 * @version:v1.0
 */
public class test322 {

    public static void main(String[] args) {
        int[] ints = {1, 2, 5};
        test322 test322 = new test322();
        System.out.println(test322.coinChange(ints, 11));

    }

    public int coinChange(int[] coins, int amount) {

        int[] ints = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            ints[i] = Integer.MAX_VALUE;
        }
        ints[0] = 0;
        for (int coin : coins) {
            for (int i = 0; i <= amount; i++) {
                if (coin <= i) {
                    ints[i] = Math.min(ints[i], ints[i - coin] + 1);
                }
            }
        }
        if(ints[amount]==Integer.MAX_VALUE){
            return -1;
        }
        return ints[amount];
    }

}
